1. Field of the Invention
This application relates generally to decoders for Low Density Parity Check (LDPC) codes, and, more specifically, to increasing the throughput of such decoders.
2. Related Art
LDPC decoders are characterized by a parity check matrix, the rows of which define parity check equations for checking whether a candidate LDPC code word is valid or not. In particular, the bits in a row of the matrix define the bits in a candidate code word that, when XORed together, must produce a zero result for a code word to be valid. When a code word satisfies, i.e., resolves to zero, all the parity check equations implied by a parity check matrix, the code word is deemed to be valid.
Current LDPC decoders, employing a check node/bit node structure that tracks the parity check equations of the parity check matrix, iterate until a predetermined exit condition is satisfied, for example, the condition when all of the parity check equations are resolved to zero, or the condition when a fixed number of iterations have been performed. Each iteration proceeds in two steps. In the first step, each of the check nodes is processed by computing the XOR of hard decision, full bit estimates for all connected bit nodes, and then generating update messages for each of these bit nodes responsive to soft decision, extrinsic bit estimates. In the second step, the hard decision, full bit estimates for the bits nodes are updated in response to the update messages. Significantly, the second step does not begin until all the check nodes have completed the first step. That in turn increases the time for the decoder to converge.
Although efforts have been made to overlap check node and bit node processing within an iteration, see US 2004/0194007, Hocevar, “Layered Low Density Parity Check Decoding For Digital Communications,” filed Mar. 23, 2004, and “A Reduced Complexity Decoder Architecture Via Layered Decoding Of LDPC Codes,” Dale E. Hocevar, IEEE SIPS 2004, pp. 107-112, and therefore increase decoder throughput, these efforts have been limited to specific LDPC codes, for example, those in which all of the columns of the parity check matrix for a group have a weight of one or less, implying that none of the check nodes within the group share the same bit node. Since LDPC codes in general violate this constraint, these efforts have not been significant.